The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


Chapter 11
Historical Remarks

Twofish originated from an attempt to take the original Blowfish design and modify it for a 128-bit block. We wanted to leverage the speed and good diffusion of Blowfish, while also improving it where we could. We wanted the new cipher to have a bijective F function, a much more efficient key schedule, and to be implementable in custom hardware and smart cards in addition to 32-bit processors (i.e., have smaller tables). And we wanted it to be even faster than Blowfish (per byte encrypted), if possible.

Initial thoughts were to have the Blowfish round structure operate on the four 32-bit subblocks in a circular structure (an incomplete Feistel network), but there were problems getting the diffusion to work in both the encryption and decryption directions. Having two parallel Blowfish round functions and letting them interact via a two-dimensional Feistel structure ran into the same problems. Our solution was to have a single Feistel structure with two Blowfish-like 32-bit round functions and to combine them using a PHT (an idea stolen from SAFER). This idea also provided nearly complete avalanche during the round.

Round subkeys are required to avoid slide attacks against identical round functions. We used addition instead of XOR to take advantage of the Pentium LEA opcode and implement them in effectively zero time.

We used 8-by-8-bit S-boxes and an MDS matrix (an idea stolen from Square, although Square uses a single fixed S-box) instead of random 8-by-32-bit S-boxes, both to simplify the key schedule and ensure that the g function is bijective. This construction ensured that Twofish would be efficient on 32-bit processors (by precomputing the S-boxes and MDS matrix into four 8-by-32-bit S-boxes) while still allowing it to be computed on the fly in smart cards. And since our MDS matrix is only ever computed in one direction, we did not have to worry about the matrix’s efficiency in the reverse direction (which Square had to consider).

The construction also gave us considerable performance flexibility. We worked hard to keep this flexibility, so implementers would have a choice of how much key pre-processing to do depending on the amount of plaintext to be encrypted. And we tried to maintain these tradeoffs for 32-bit microprocessors, 8-bit microprocessors, and custom hardware.

Since one goal was to be able to keep the complete design in our heads, any complication that did not have a clear purpose was deleted. Additional complications we chose not to introduce were key-dependent MDS matrices or round-dependent variations on the byte ordering and the PHT. We also toyed with the idea of swapping 32-bit words within the Feistel halves (something we called the “twist”), but abandoned it because we saw no need for the additional complexity.

We did keep in the one-bit rotations of the target block, primarily to reduce the vulnerability to any attack based on byte boundaries. The particular manifestation of this one-bit rotation was due to a combination of performance and cryptanalytic concerns. Larger rotations would be slower in some implementations, and simpler constructions were less secure.

We considered using all the key bytes, rather than just half, to define the key-dependent S-boxes. Unfortunately, this made the key setup time for high-end machines unreasonably large, and also made encryption too slow on low-end machines. By dropping this to half the key bits, these performance figures were improved substantially. By carefully selecting how the key bytes were folded down to half their size before being used to generate the cipher’s S-boxes, we were able to ensure that pairs of keys with the same S-boxes would have very different subkey sequences.

The key schedule gave us the most trouble. We had to resist the temptation to build a cryptographic key schedule like the ones used by Blowfish, Khufu, and SEAL, because low-end implementations needed to be able to function with minimal additional memory and, if necessary, to compute the subkeys as needed by the cipher. However, a simple key schedule can be an important weak point in a cipher design, leaving the whole cipher vulnerable to partial-key guessing attacks, related-key attacks, or to attacks based on waiting for especially weak keys to be selected by a user. Though our final key schedule is rather complex, it is conceptually much simpler than many of our intermediate designs. Reusing many of the primitives of the cipher (each round’s subkeys are generated by a computation nearly identical to the one that goes on inside the round function, except for the specific inputs involved) made it possible to investigate properties of both the key schedule and of the cipher at the same time.

We spent considerable time choosing q0 and q1. Since these provide the primary non-linearity in the cipher, they had to be strong. We wanted to be able to construct them algebraically for applications where storing 512 bytes of fixed tables was not possible. In the end, we built permutations from random parameters, and tested the permutations against our required criteria.

The name “Twofish” reared its head late in the design process. We tried various names beginning with “Blow” or ending with “fish.” The name Twofish was chosen for several reasons: it is traditional to name ciphers after sea creatures, and animals in general; no one liked “Blowfish II”; the round function originally derived from two Blowfish round functions in parallel; and of course, there is Dr. Seuss [Seu60].1


1For readers who did not grow up in North America: Dr. Seuss was a famous writer of children’s books, one of which is called One Fish, Two Fish, Red Fish, Blue Fish. The marketing tie-ins were too lucrative to ignore.

And finally, we cryptanalyzed Twofish. We cryptanalyzed and cryptanalyzed and cryptanalyzed, right up to the morning of the submission deadline. Since then we have cryptanalyzed more, and are continuing to do so. There’s no stopping.


Previous Table of Contents Next